// https://www.lintcode.com/problem/remove-node-in-binary-search-tree/description
// 87. 删除二叉查找树的节点
// 给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。

// 样例
// 给出如下二叉查找树：

//           5

//       /    \

//     3          6

//  /    \

// 2       4

// 删除节点3之后，你可以返回：

//           5

//       /    \

//     2          6

//       \

//          4

// 或者：

//           5

//       /    \

//     4          6

//  /   

// 2



/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param value: Remove the node with given value.
     * @return: The root of the binary search tree after removal.
     */
    
    
    // 不要怕分类，有时反而省事！
    // 分治法
    // 三种大情况

    // - 节点的值大于目标，那么去右子树去删除节点
    // - 小于目标，去左子树
    // - 等于目标
    // a 节点是叶子，直接删除节点即可
    // b 节点只有一个子节点，那么就让这个子节点代替节点（用节点指针替换，不然还要删）
    // c 节点有两个子节点，按遍历顺序，用左子树最右节点替换给当前节点（用值替换，否则原先指针后面的都丢失了）
    
    // 指针替换需要记pre，节点值替换不需要
    void assign(TreeNode * root, TreeNode * node, TreeNode * new_node)
    {
        if (root->left == node)
        {
                root->left = new_node;
        }
        else
        {
                root->right = new_node;
        }
    }
    
    void removeN (TreeNode * pre, TreeNode * root, int value)
    {
        if (!root)
        {
            return;
        }
        if (root->val == value)
        {
            if (!root->left && !root->right)
            {
                assign(pre, root, NULL);
            }
            else if (!root->left)
            {
                assign(pre, root, root->right);
            }
            else if (!root->right)
            {
                assign(pre, root, root->left);
            }
            else
            {
                TreeNode * tmp = root->left;
                while (tmp->right)
                {
                    tmp = tmp->right;
                }
                root->val = tmp->val;
                // tmp = NULL;
                removeN(root, root->left, tmp->val); // 注意可能有左子树
            }
        }
        else if (root->val > value)
        {
            pre = root;
            removeN(pre, root->left, value);
        }
        else
        {
            pre = root;
            removeN(pre, root->right, value);
        }
    }
    
    TreeNode * removeNode(TreeNode * root, int value) {
        TreeNode * head = new TreeNode(-1);
        head->left = root;
        TreeNode * pre = head;
        removeN(pre, root, value);
        return head->left;
    }
    
    
};